//深搜 深度优先搜索 dfs
#include <cstdio>
#include <algorithm>

using namespace std;
/*
//这里可以选1和2和3
1
    // 这里可以选2和3
    2
        // 这里可以选3
        3
        输出 1 2 3
    3
        // 这里可以选2
        2
        输出 1 3 2
2
    // 这里可以选1和3
    1
        3 输出 2 1 3
    3
        1 输出 2 3 1
3
 ·······
*/

// 所以只要解决一个问题，就是现在可以选哪些数
// 用一个数组来记录下已经用的数，剩下的数就是能用的

// 数组大小比要求大就行，最好不要刚刚好那么大
bool used[16];
// 这个数组记录已经搜索到的数，每次递归进去就更新一遍
// 比如depth为0时就更新第一个数
int nums[16];
// 用这个depth记录深度，depth==n时直接返回（方便一点，就不用判断used是不是全部都是true了）
// 用这个n表示，，，输入n
void dfs(int n, int depth)
{
    int i;
    // 递归我习惯先确定结束时的条件
    if (depth == n)
    {
        for (i = 0; i < n; i++)
        {
            // 把已经搜索到的数都打印出来
            printf("%5d", nums[i]);
        }
        printf("\n");
        return;
    }
    
    // 就比如depth=0, 也就是要找第一个数
    // 那第一个数肯定就是在1-n里面的
    // 现在这里要遍历一遍可以用的数
    for (i = 1; i <= n; i++)
    {
        if (used[i])
        {
            // 如果这个数字已经用过了，就不进去了（相当于不用它了）
            continue;
        }
        // 更新nums的值
        nums[depth] = i;
        // 刚刚少了一步就是把用过的数更新一下
        used[i] = true;
        // 进去找下一个数
        dfs(n, depth + 1);
        // 从这里出来其实后面的数都已经找了一遍了，比如刚刚用的1，现在1就可以被后面的数用了
        used[i] = false;
    }
}

int main(int argc, char const *argv[])
{
    dfs(3, 0);
    return 0;
}
